1800F - Dasha and Nightmares - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;

constexpr int inf = 0x3f3f3f3f;
constexpr ll infll = 0x3f3f3f3f3f3f3f3f;
constexpr double EPS = 1e-8;
constexpr double PI = atan(1) * 4;

template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T> inline bool chmax(T& x, T y) {return x < y ? x = y, 1 : 0;}
template <typename T> inline bool chmin(T& x, T y) {return x > y ? x = y, 1 : 0;}
inline int LSB(int i) {return (i & -i);}

/*
    - Read carefully
    - Look for patterns/observations
    - Think backwards
*/

constexpr int maxn = 2e5+5;

int n, cnt[maxn][30], curmask[maxn], sign[maxn];
ll res = 0;
unordered_map <int, int> masks[2][27];
string s[maxn];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> s[i];

        sign[i] = ((int)s[i].length()) % 2;

        for (char c : s[i]){
            curmask[i] ^= (1 << (c - 'a'));
            cnt[i][c - 'a']++;
        }

        for (int j = 0; j < 26; j++){
            if (!cnt[i][j]) masks[sign[i]][j][curmask[i]]++;    
        }
    }    

    for (int i = 1; i <= n; i++){
        // Try all letters it doesn't have
        for (int j = 0; j < 26; j++){
            if (!cnt[i][j]){
                res += masks[sign[i] ^ 1][j][((1 << 26) - 1) ^ curmask[i] ^ (1 << j)];
            }
        }
    }

    cout << res / 2 << endl;
    return 0;
}